package solution;

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int m = matrix[0].length;

        //对每一行使用二分
        for (int i = 0; i < n; i++) {
            int left = 0, right = m - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (matrix[i][mid] < target) {
                    left = mid + 1;
                } else if (matrix[i][mid] == target) {
                    return true;
                } else {
                    right = mid;
                }
            }
            if (left >= 0 && left < m && matrix[i][left] == target) {
                return true;
            }
        }

        return false;
    }
}